/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */ 
import java.util.ArrayList;
import java.util.HashMap;
public class copyList {
  // Use a stack to keep track of the stack growth
  //ArrayList<RandomListNode> origList = new ArrayList<RandomListNode>();
  //ArrayList<RandomListNode> newList = new ArrayList<RandomListNode>();
  
  public RandomListNode copyRandomList(RandomListNode head) {
    // Note: The Solution object is instantiated only once and is reused by each test case.
    
    if (head == null) return null;
    
    RandomListNode newHead = new RandomListNode(head.label);
    RandomListNode curNode = head, curNewNode = newHead;
    HashMap<RandomListNode, RandomListNode> nodeMap = new HashMap<RandomListNode, RandomListNode>();

    while (curNode.next != null) {
      nodeMap.put(curNode, curNewNode);
      RandomListNode newNode = new RandomListNode(curNode.next.label);
      newNode.random = null;
      curNewNode.next = newNode;
      curNewNode = newNode;
      curNode = curNode.next;
    }
    
    // reiterate one more time and handle random
    curNode = head;
    curNewNode = newHead;
    while (curNode.next != null) {
      if (curNode.random != null) {
        curNewNode.random = nodeMap.get(curNode.random);
      }
      curNode = curNode.next;
      curNewNode = curNewNode.next;
    }
    
    /*RandomListNode newHead = new RandomListNode(head.label);
    RandomListNode cur_node_in_orig = null;
    RandomListNode cur_node_in_new = null;
    origList.add(head);
    newList.add(newHead);

    // Use queue to apply BFS
    while (!origList.isEmpty()) {
      cur_node_in_orig = origList.remove(0);
      cur_node_in_new = newList.remove(0);
      // push its random and next to the stack
      if (cur_node_in_orig.next != null) {
        RandomListNode newNode = new RandomListNode(cur_node_in_orig.next.label);
        cur_node_in_new.next = newNode;
        origList.add(cur_node_in_orig.next);
        newList.add(newNode);
      }
      if (cur_node_in_orig.random != null) {
        RandomListNode newNode = new RandomListNode(cur_node_in_orig.random.label);
        cur_node_in_new.next = newNode;
        origList.add(cur_node_in_orig.random);
        newList.add(newNode);
      }
    }*/
    
    
    
    return newHead;
  }
}